Most general purpose computer systems support a display of text-based characters, including letters, numerals, and other symbols, on pixel-oriented display devices. A pixel is a discrete segment of an overall field in which an image can be displayed. Although pixels are typically square or round in shape for most devices, many newer pixel-oriented display devices include rectangular pixels. A pixel is activated or "turned on" when the process that generates the display determines that it is appropriate to activate that portion of the image field. Accordingly, the display surface for a pixel-oriented display device consists of a grid of points, or pixels, each of which can be individually illuminated or "darkened" to display an image. Common pixel-oriented display devices are raster scan cathode ray tube (CRT) displays, liquid crystal display (LCD) displays, dot matrix printers, and laser printing devices.
In general, to display text on a pixel-oriented display device, a computer system utilizes one or more fonts. A font is a collection of characters designed by a typographer in a consistent style. Specifically, a typographer designs a character outline or "glyph" of each character for a particular font, including characters, numbers, punctuation, and any other image for a given font. A particular font refers to selected geometric characteristics of the characters within a character set. A glyph for a given character in a font is described as a numbered sequence of points that are on or off a curve defining the boundary of the character. In general, number sequence for the points should follow a recognized rule for how the points relate to the area to be filled and the area not to be filled when rendering the glyph. For TrueType font descriptions, the points are numbered in consecutive order so that as a path is traversed in the order of increasing point numbers, the filled area will always be to the right of the path. This glyph or outline description of the character is typically stored within a font file maintained by the computer system. TrueType font files are described in the Technical Specification, Revision 1.5, January 1994, entitled "TrueType 1.0 Font Files," by Microsoft Corporation, Redmond, Wash.
In response to the information supplied by a font file, the outline is scaled according to the font size requested by the user and the characteristics of the display device on which it is to be displayed. The outline also may contain hints, which are routines that, when executed, adjust the shapes of the character outlines for various point sizes to improve their appearance. The outline is then scan converted to produce a character bitmap that can be rendered on the selected display device.
A character bitmap represents a grid-like array of pixels and each array element contains a pixel center. The pixel centers are connected in either horizontal or vertical directions by straight lines commonly described as scan lines or reference lines. Each character bitmap contains data reflecting which pixels in a subset of the display grid must be illuminated in order to form an image of a particular character. When a computer system needs to display a particular character at a display location, it accesses the character bitmap for that character. The computer system then turns the illumination of pixels near the display location on or off in accordance with the data stored in the character bitmap. The concept of displaying a character extends to a temporary display, such as a CRT display, as well as a more permanent image creation in the form of a printer.
Using font descriptions, computer systems can now create character bitmaps defining the images to be displayed, also described as raster fonts, dynamically in different typefaces in response to the needs of users. A computer program, which is also described as a rasterizer program, is typically incorporated as part of an operating system or printer control software program to provide this font technology service. The rasterizer program may be called by an application program, such as a word processor or a spreadsheet, when the program requires a raster font. In response to this request, the rasterizer program reads a description of the character outline from a font file stored within a memory storage device. The font file can be stored within either volatile or nonvolatile memory of the computer system or the display device.
The rasterizer program also receives the character's height or "point" size and the predetermined resolution of the intended display device to support the scaling of the character outline. The resolution of a pixel-oriented display device is specified by the number of dots or pixels per inch (dpi) that are to be displayed. This information supports a mapping of the description of the character outline into physical pixel units for the display device to be employed in displaying the character in that particular size. Thus, the geometric description of the character outline is scaled in physical pixel coordinates and represents a function of the predetermined physical pixel size of the display device and the requested point size. This process alters the height and width of the character.
To support the rendering of fonts at low resolution and/or small sizes, the rasterizer program typically includes a routine that analyzes the outlines of fonts and "hints" the fonts according to the size specified by the user in the resolution of the display device. The fundamental task of hinting is to identify critical characteristics of the original font design and to use instructions which adjust the outline to insure that those characteristics will be preserved when the character outline is rendered in different sizes on different devices. Common hinting goals include consistent stem weights, consistent intensity, even spacing, and the elimination of pixel dropouts.
If required, the rasterizer program applies hints to the scaled character outline to fit it to pixel boundaries while distorting the scaled character outline as little as possible. The rasterizer program thereafter conducts a scan conversion operation for the hinted character outline by superimposing a grid corresponding to the horizontal and vertical densities of the intended display device over the hinted outlines, then designating the subset of pixels of the grid whose centers fall within, or precisely on, the hinted outlines as pixels requiring illumination by the display device. The rasterizer program then returns the resulting raster font to the application program, which may use it to display text. The raster font also may be stored within an allocated buffer of computer system memory or display device memory to be used to satisfy any identical request received in the future.
The scan conversion process represents the task of "coloring" inside the lines of the character. For the rasterizer program, a scan converter generates a character bitmap which includes pixels which are activated based upon the relationship of the pixel centers with the character outlines. For conventional scan converters, two rules are generally used to determine if a particular pixel should be turned on or turned off, First, if a pixel's center or reference point falls within the character outline, that pixel is turned on and becomes part of that character outline. Second, if a contour of the character outline falls exactly on a pixel's center, that pixel is turned on. These rules define the conventional "centerpoint" fill method of bitmapping a character outline or glyph and is well known in the art of digital typography.
In general, at the start of a conventional scan conversion process, the character outline is traversed to determine the maximum and minimum coordinate values of the outline. The amount of memory required for the computer system to support the scan conversion tasks is then estimated to insure sufficient workspace memory for the storage of calculation results generated by the rendering operation. Each contour of the character outline is subsequently broken into individual segments of lines and splines and these segments are rendered. The rendering process detects each occurrence of an intersection of a scan line with one of the representations of a line segment or spline segment. Each scan line intersection represents a transition having a particular transition sense, i.e., an on-transition or an off-transition. For each detected transition, a transition entry containing the transition location is stored within a data array called a transition table. Depending upon the sense of the transition entry, the transition entry is stored within either the "ON" transition table or the "OFF" transition table. These transition entries are typically sorted by ascending order of the scan lines to support the creation of a character bitmap. Each transition having an "ON" sense is paired with its corresponding transition having an "OFF" sense and the pixels associated with the scan line are set or "filled" for the character bitmap. The character bitmap defines the pixels to be activated for supplying an image of the character on a connected display device.
Reviewing now certain aspects of the scan conversion process, one method for estimating the amount of workspace memory to support scan conversion tasks is to multiply the number of scan lines in the character bitmap times the maximum possible intersections of a character outline per scan line. The maximum possible intersections per scan line is calculated by traversing the character outline and counting the characater's local maxima and minima, which are also described as "reversals" in direction. Although this method represents a simple computational solution for the memory estimate, it supplies an overly conservative estimate of workspace memory for character outlines with small details. Accordingly, there is a need for an improved method that defines a more efficient use of memory to support scan conversion tasks. The present invention provides an improved method for allocating memory workspace by accurately calculating memory requirements for character outlines with either large details or many small details, thereby supporting the efficient use of this computer resource.
The use of splines to represent outline curves is known in font technologies. One technique for rendering a spline is to break it into short line segments and then to render those segments sequentially by using a parametric equation to define the short line segments. However, the use of a parametric equation to render a spline supplies only an approximate representation of the actual curve. In addition, to obtain a reasonably accurate approximation, a large number of line segments must be used to represent the character outline. This increases the number of calculations, thereby increasing the time required to render the spline. Accordingly, there is a need in the art for a method of rendering splines that is both faster and more accurate than the above-described conventional technique. The present invention implements an implicit rendering algorithm based on a second order equation for a parabola to achieve improvements in speed and character image quality.
In general, rendering a bounded character outline or shape produces for a given scan line both an on-transition and an off-transition based upon the entering and exiting intersections of the scan line with the character outline. However, the concept that a bounded shape intersects a given scan line in matched pairs of transitions breaks down when the scan line contacts extrema of the shape, or when an endpoint of the shape is coincident with scan lines. The present invention addresses the special case of rendering an endpoint on a scan line by supplying a structured approach that examines all geometric possibilities for approaching and exiting the endpoint to determine whether the pixel associated with the endpoint should be activated.
As pixel-oriented display devices have achieved higher resolution characteristics, it has become possible to display text in smaller-sized characters on these devices while still maintaining readability. However, as physical character size becomes smaller for a display device of a given resolution, sampling error distortion can occur. Accordingly, after making an initial determination for which pixels to turn on, the contour of the character outline is analyzed to detect one type of sampling error that commonly occurs when displaying characters of a given font on a pixel-oriented display device, an error called "dropout." A dropout condition may be defined as an interior region of a character outline that passes through a scan line and between adjacent pixels in which neither pixel has been turned on in accordance with the previously described Rules 1 and 2. In other words, a dropout condition occurs when the space within the character outlines become so narrow that this contour portion misses one or more pixel centers.
If a dropout control technique is not used to correct the dropout condition, the decision-making algorithm for activating a pixel may determine that a particular pixel should not be activated, thereby causing a break at a point in a character that the viewer would expect to be a continuous line. Although this problem will naturally arise even if the physical size of the character to be displayed is rather large (if the resolution of the display device is low, or if the character features are very thin), it is mostly problematic when characters are to be displayed with a small physical size.
It is known that the subjective response of a reader to dropout is to prefer having a pixel illuminated, even if it tends to geometrically distort the character, over a situation in which an inappropriate discontinuity occurs in the strokes of the character. Therefore, the art has addressed the subject of dropout control so that the results in a displayed image is most pleasing to viewers. A conventional technique for addressing the dropout problem is to always activate the pixel on the left for a horizontal pair of pixels and, for a vertical pair of pixels, to always activate the pixel below. From a typographical view, this convention produces a less than desirable result. Another technique is to always illuminate the pixel located nearest the contour of the character outline. This generally provides a displayed image having an appearance preferred by viewers because it preserves the symmetry of the character outline. However, this approach requires knowledge and storage of intersections of the character outline with the scan lines, or transitions, in sub-pixel precision, thereby increasing the processing time and memory requirements for scan conversion. The present invention provides an improved solution for the dropout condition by reducing the number of calculations required to obtain sub-pixel accuracy for the rendering of line segments and splines.
In summary, the present invention provides an improved scan converter to support the efficient and accurate display of character outlines by pixel-oriented display devices. To conserve the finite resource of memory, the present invention supports an efficient use of available memory workspace by accurately determining an upper bound for the amount of memory required to support scan conversion calculations. To achieve improvements in speed and character image quality, the present invention renders the spline segments of a character outline by using a quadratic equation to calculate an implicit function based on the spline control points. The present invention further addresses in a systematic manner the rendering of an endpoint located on a scan line to determine whether the pixel associated with the endpoint should be activated. This decision is based upon the direction of approach to and exit from this endpoint for the pair of segments connected to the endpoint. The present invention also reduces the number of calculations requiring sub-pixel precision to support the selection of the pixel located nearest the contour, thereby providing an improved solution for dropout condition.